import java.util.*;

public class Leet1029 {

    public static void main(String[] args) {
        Leet1029 l = new Leet1029();
        System.out.println(l.twoCitySchedCost(new int[][]{{259,770},{448,54},{926,667},{577,469}}));
    }

    public int twoCitySchedCost(int[][] costs) {
        int num = 0,len = costs.length;
        int[][] a = new int[len][2];
        for (int i = 0; i < len; i++) {
            a[i][0] = i;
            a[i][1] = costs[i][1]-costs[i][0];
        }
        Arrays.sort(a,((o1, o2) -> o2[1]-o1[1]));
        for (int i = 0; i < len/2; i++)
            num+=costs[a[i][0]][0];
        for (int i = len-1; i >= len/2; i--)
            num+=costs[a[i][0]][1];
        return num;
    }
}
